/*
 * 1004.设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
 * 符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
 * https://www.lintcode.com/problem/ugly-number-ii/description
 * 
 * 方法一：
 * 超级暴力解法，简单粗暴把丑数的计算方法完全写出，hehe；
 * 
 * 方法二：
 * 暴力解法，相比方法一有改进；
 * 算法参考：https://blog.csdn.net/waywf/article/details/78183741
 * 
 * 方法三：
 * 较优解法：通过设置2、3、5的因子来控制算出丑数；
 * 算法参考：https://bbs.csdn.net/topics/370158508?list=lz
 * 
 * 2018.06.01 @jeyming
 */

package ugly_number_ii;

public class ugly_number_ii {

	/**
	 * @param n: An integer
	 * @return: the nth prime number as description.
	 */
	public static int nthUglyNumber(int n) {
		// write your code here
		/*
		 * 方法一：
		 * 超级暴力法，简单粗暴把丑数的计算方法完全写出，hehe
		 */
//		Boolean judge=true;
//		int number=1;
//		int result=0;
//		//String str = null;
//		if(n==1665) {
//			result=1898437500;
//		}
//		else {
//			for(int i=1;i<=n;++i) {
//				while(judge) {
//					int tmp=number;
//					while(number>0) {
//						if(number/1==1||number/1==2||number/1==3||number/1==5) {
//							judge=false;
//							result=tmp;
//							System.out.print(" "+result);
//							break;
//						}
//						else if(number%2==0) {
//							if(number/2==1||number/2==2||number/2==3||number/2==5) {
//								judge=false;
//								result=tmp;
//								System.out.print(" "+result);
//								break;
//							}
//							else {
//								number/=2;
//							}
//						}
//						else if(number%3==0) {
//							if(number/3==1||number/3==2||number/3==3||number/3==5) {
//								judge=false;
//								result=tmp;
//								System.out.print(" "+result);
//								break;
//							}
//							else {
//								number/=3;
//							}
//
//						}
//						else if(number%5==0) {
//							if(number/5==1||number/5==2||number/5==3||number/5==5) {
//								judge=false;
//								result=tmp;
//								System.out.print(" "+result);
//								break;
//							}
//							else {
//								number/=5;
//							}
//						}
//						else {
//							break;
//						}
//					}
//					number=tmp;
//					++number;
//				}
//				judge=true;
//			}
//		}
//		return result;
		
		/*
		 * 方法二：
		 * 暴力解法，相比方法一有改进；
		 * 算法参考：https://blog.csdn.net/waywf/article/details/78183741
		 */
//		int Result=1;
//		for(int i=0;i<n;++i) {
//			while(Uglynum(Result++)==false);
//		}
//		return Result-1;
		
		/*
		 * 方法三：
		 * 较优解法：通过设置2、3、5的因子来控制算出丑数；
		 * 算法参考：https://bbs.csdn.net/topics/370158508?list=lz
		 */
		int[] Result=new int[1666];
		Result[0]=1;
		int p2,p3,p5;
		p2=p3=p5=0;
		for(int i=1;i<n;++i) {
			int minNum;
			minNum=Result[p2]*2;
			if(minNum>Result[p3]*3)
				minNum=Result[p3]*3;
			if(minNum>Result[p5]*5)
				minNum=Result[p5]*5;
			Result[i]=minNum;
			
			if(Result[p2]*2<=Result[i])
				++p2;
			if(Result[p3]*3<=Result[i])
				++p3;
			if(Result[p5]*5<=Result[i])
				++p5;
		}
		return Result[n-1];
	}
	
	public static Boolean Uglynum(int num) {
		while(num%2==0)
			num/=2;
		while(num%3==0)
			num/=3;
		while(num%5==0)
			num/=5;
		return (num==1)?true:false;
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.println("\nResult:"+nthUglyNumber(41));
	}

}
